package cn.initcap.algorithm.graph;

import java.io.File;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * 稠密图 - 邻接矩阵
 *
 * @author initcap
 * @date Created in 1/20/19 8:34 PM.
 */
public class DenseWeightedGraph<Weight extends Number & Comparable> implements Graph<Edge<Weight>, Weight> {

    /**
     * 节点数
     */
    private int node;
    /**
     * 边数
     */
    private int margin;
    /**
     * 是否为有向图
     */
    private boolean directed;
    /**
     * 记录入度和出度
     */
    private int[] indegree, outdegree;
    /**
     * 图的具体数据
     */
    private Edge<Weight>[][] g;

    public DenseWeightedGraph(String filename, boolean directed) {
        this.directed = directed;
        File file = new File(filename);

        try (Scanner scanner = new Scanner(file)) {

            node = scanner.nextInt();
            if (node < 0) {
                throw new IllegalArgumentException("node must be non-negative");
            }
            indegree = new int[node];
            outdegree = new int[node];
            int e = scanner.nextInt();
            if (e < 0) {
                throw new IllegalArgumentException("margin must be non-negative");
            }

            for (int i = 0; i < e; i++) {
                int a = scanner.nextInt();
                int b = scanner.nextInt();
                Double weight = scanner.nextDouble();
                if (a == b) {
                    throw new IllegalArgumentException("Self Loop is Detected!");
                }
                if (directed) {
                    indegree[b]++;
                    outdegree[a]++;
                }
                addEdge(new Edge(a, b, weight));
            }
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    @Override
    public int nodeSize() {
        return node;
    } // 返回节点个数

    @Override
    public int marginSize() {
        return margin;
    } // 返回边的个数

    /**
     * 向图中添加一个边
     *
     * @param e
     */
    @Override
    public void addEdge(Edge e) {
        validateVertex(e.v(), node);
        validateVertex(e.w(), node);
        if (g == null) {
            // g初始化为n*n的布尔矩阵, 每一个g[i][j]均为null, 表示没有任和边
            // false为boolean型变量的默认值
            g = new Edge[node][node];
            for (int i = 0; i < node; i++) {
                for (int j = 0; j < node; j++) {
                    g[i][j] = null;
                }
            }
        }

        if (hasEdge(e.v(), e.w())) {
            return;
        }

        g[e.v()][e.w()] = new Edge(e);
        if (e.v() != e.w() && !directed) {
            g[e.w()][e.v()] = new Edge(e.w(), e.v(), e.wt());
        }

        margin++;
    }

    /**
     * 验证图中是否有从v到w的边
     *
     * @param v
     * @param w
     * @return
     */
    @Override
    public boolean hasEdge(int v, int w) {
        validateVertex(w, node);
        validateVertex(v, node);
        return g[v][w] != null;
    }

    /**
     * 显示图的信息
     */
    @Override
    public void show() {

        for (int i = 0; i < node; i++) {
            for (int j = 0; j < node; j++) {
                if (g[i][j] != null) {
                    System.out.print(g[i][j].wt() + "\t");
                } else {
                    System.out.print("NULL\t");
                }
            }
            System.out.println();
        }
    }

    /**
     * 返回图中一个顶点的所有邻边
     * 由于java使用引用机制，返回一个Vector不会带来额外开销,
     *
     * @param v
     * @return
     */
    @Override
    public Iterable<Edge<Weight>> adj(int v) {
        validateVertex(v, node);
        List<Edge<Weight>> adjV = new ArrayList<>();
        for (int i = 0; i < node; i++) {
            if (g[v][i] != null) {
                adjV.add(g[v][i]);
            }
        }
        return adjV;
    }

    @Override
    public int indegree(int v) {
        if (!isDirected()) {
            throw new IllegalArgumentException("undirected graph no indegree!");
        }
        return this.indegree[v];
    }

    @Override
    public int outdegree(int v) {
        if (!isDirected()) {
            throw new IllegalArgumentException("undirected graph no outdegree!");
        }
        return this.outdegree[v];
    }

    @Override
    public boolean isDirected() {
        return this.directed;
    }

}
